#include "find.h"
namespace wanghao
{
    #define BLOCK_SIZE 4
    //暴力查找算法
    int Find::SequentialSearch(int* arr,int sz,int k)
    {
        assert(arr);
        //循环遍历数组
        for(int i = 0;i < sz;i++)
        {
            //判断当前的值是否等于k(要查找的值)
            if(*(arr + i) == k)
            {
                return i;
            }
        }
        return -1;
    }
    //二分查找
    int Find::BinarySearch(int* arr,int sz,int k)
    {
        assert(arr);
        //计算left和right的值
        int left = 0;
        int right = sz - 1;
        while(left <= right)
        {
            //计算中间的值
            int mid = left + (right - left) /2;
            //判断,然后更新left值
            if(*(arr + mid) < k) left = mid + 1;
            //判断,然后更新right值
            else if(*(arr + mid) > k) right = mid - 1;
            //如果相等就返回下标
            else if(*(arr + mid) == k) return mid;
        }
        //没找到就返回-1
        return -1;
    }
    // 比较函数
    int Find::compare(const void *a, const void *b)
    {
        return (*(int*)a - *(int*)b);
    }
    //分块查找
    int Find::BlockSearch(int* arr, int sz, int k) 
    {
        assert(arr);
        int blockSize = BLOCK_SIZE;
        int numBlocks = (sz + blockSize - 1) / blockSize; // 向上取整
        int *index = (int*)malloc(numBlocks * sizeof(int)); // 索引数组
        
        // 构建索引数组
        for (int i = 0; i < numBlocks; i++)
        {
            int blockStart = i * blockSize;
            int blockEnd = (i + 1) * blockSize - 1;
            if (blockEnd >= sz) blockEnd = sz - 1;
            *(index + i) = *(arr + blockEnd); // 存储每块的最大值
        }
        // 在索引数组中进行二分查找，找到包含目标值的块
        int left = 0, right = numBlocks - 1;
        int blockIndex = -1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (k <= index[mid])
            {
                blockIndex = mid;
                right = mid - 1;
            }
            else left = mid + 1;
        }
        // 在找到的块内进行顺序查找
        if (blockIndex != -1)
        {
            int blockStart = blockIndex * blockSize;
            int blockEnd = (blockIndex + 1) * blockSize - 1;
            if (blockEnd >= sz)
            {
                blockEnd = sz - 1;
            }
            for (int i = blockStart; i <= blockEnd; i++)
            {
                if (arr[i] == k)
                {
                    free(index);
                    return i; // 返回元素的位置
                }
            }
        }
    
        free(index);
        return -1; // 未找到目标元素
    }
    // 插值查找函数
    int Find::InterpolationSearch(int* arr, int sz, int k)
    {
        assert(arr);
        int low = 0, high = sz - 1;
        while (low <= high && k >= *(arr + low) && k <= *(arr + high))
        {
            // 当元素均匀分布时，使用插值公式计算位置
            if (high == low)
            {
                if (arr[low] == k) return low;
                return -1;
            }
            // 计算插值位置
            int pos = low + ((double)(high - low) / (*(arr + high) - arr[low])) * (k - *(arr + low));
            // 检查插值位置的值
            if (*(arr + pos) == k) return pos;
            // 如果x大于arr[pos]，则忽略左半部分
            if (*(arr + pos) < k) low = pos + 1;
            // 如果x小于arr[pos]，则忽略右半部分
            else high = pos - 1;
        }
        // 未找到目标值
        return -1;
    }
    //辅助函数，用于计算两个整数中的较小值
    int Find::min(int x, int y)
    {
        return (x < y) ? x : y;
    }
    //斐波那契查找算法
    int Find::FibonacciSearch(int* arr, int sz, int k)
    {
        //初始化斐波那契数
        int fibMMm2 = 0;
        int fibMMm1 = 1;
        int fibM = fibMMm2 + fibMMm1;
        //找到大于或等于n的最小斐波那契数
        while (fibM < sz)
        {
            fibMMm2 = fibMMm1;
            fibMMm1 = fibM;
            fibM = fibMMm2 + fibMMm1;
        }
        // 标记被排除的范围的起始位置
        int offset = -1;
        // 当还有元素需要检查时
        while (fibM > 1)
        {
            // 检查fibMMm2是否是一个有效的索引
            int i = min(offset + fibMMm2, sz - 1);
            // 根据arr[i]与x的比较结果来缩小搜索范围
            if (arr[i] < k)
            {
                fibM = fibMMm1;
                fibMMm1 = fibMMm2;
                fibMMm2 = fibM - fibMMm1;
                offset = i;
            }
            else if (arr[i] > k)
            {
                fibM = fibMMm2;
                fibMMm1 -= fibMMm2;
                fibMMm2 = fibM - fibMMm1;
            }
            else return i;//找到元素，返回索引
        }
        // 检查最后一个可能的元素
        if (fibMMm1 && offset + 1 < sz && arr[offset + 1] == k) return offset + 1;
        // 元素未找到，返回-1
        return -1;
    }
    //交换函数
    void Find::Swap(int& x,int& y)
    {
        int z = x;
        x = y;
        y = z;
    }
    //快排hoare版本找基准值
    int Find::_QuickSort(int* arr,int left,int right)
    {
        int keyi= left;
        left++;
        while(left <= right)
        {
            while(left <= right && *(arr + right) > *(arr + keyi)) right--;
            while(left <= right && *(arr + left) < *(arr + keyi)) left++;
            if(left <= right) Swap(*(arr + right--),*(arr + left++));
        }
        Swap(*(arr + right),*(arr + keyi));
        return right;
    }
    //快排
    void Find::_QuickSort_(int* arr,int left,int right)
    {
        if(left >= right) return;
        int keyi = _QuickSort(arr,left,right);
        _QuickSort_(arr,left,keyi - 1);
        _QuickSort_(arr,keyi + 1,right);
    }
    //封装快排
    void Find::QuickSort(int* arr,int sz)
    {
        _QuickSort_(arr,0,sz - 1);
    }
    //堆向下调整算法
    void Find::AdjustDown(int* arr,int sz,int parent)
    {
        int child = 2 * parent + 1;
        //建小堆
        while(child < sz)
        {
            if(child + 1 < sz && *(arr + child) > *(arr + child + 1))
            {
                child++;
            }
            if(*(arr + child) < *(arr + parent))
            {
                Find::Swap(*(arr + child) , *(arr + parent));
                parent = child;
                child = 2 * parent + 1;
            }
            else break;
        }
    }
}